import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Stack;

public class TestSort {
    public int tmp;
    public void insort(int[] array){
        for (int i = 1; i <array.length ; i++) {
            tmp=array[i];
            int j=i-1;
            for (; j >=0 ; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j+1]=tmp;
        }


    }
    public  void shellSort(int[] array,int gap){
        for (int i = gap; i <array.length ; i++) {
            int tmp=0;
            tmp=array[i];
            int j=i-gap;
            for (; j >=0 ; j-=gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }
    public  void shell(int[] array) {
      /*  int[] drr={5,2,1};
        for (int i = 0; i < drr.length; i++) {
           shellSort (array,drr[i]);
        }
    }*/
        int gap=array.length;
        while (gap>1){

            shellSort(array,gap);
            gap=gap/2;
        }
    }
    public void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int tmp=i;
            for (int j = i+1; j <array.length ; j++) {
                if (array[tmp] > array[j]) {
                    tmp = j;
                }
            }
            int swap=array[tmp];
            array[tmp]=array[i];
            array[i]=swap;
        }
    }
    public void selectSort2(int[] array){
        for (int i = 0; i < array.length; i++) {
            int tmp=i;
            int max=array.length-1;
            for (int j = i+1; j <array.length ; j++) {
                if (array[tmp] > array[j]) {
                    tmp = j;
                }
                if (array[max]<array[j]){
                    max=j;
                }
            }
            int swap=array[tmp];
            array[tmp]=array[i];
            array[i]=swap;
            int coll=array[max];
            array[max]=array[array.length-1];
            array[array.length-1]=coll;
        }
    }
    public  void selectSort3(int[] array){
        int left=0;
        int right=array.length-1;
        while (left<right){
            int minIndex=left;
            int maxIndex = left;
            for (int i = left+1; i <=right; i++) {
                if (array[i]<array[minIndex]){
                    minIndex=i;
                }
                if (array[maxIndex]<array[i]){
                    maxIndex=i;
                }
            }
            swap(array,left,minIndex);
            if (left==maxIndex){
                maxIndex=minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
    public static void swap(int[] array,int i ,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public void heapSort1 (int[] array){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        int usedSized=array.length;
        for (int i = 0; i < array.length; i++) {
            priorityQueue.offer(array[i]);
        }
        swap(array,0,usedSized-1);
        shiftDown(array,0,usedSized);
        usedSized--;

    }
    public static void heapSort(int[] array){
        createHeap(array);
        int end=array.length-1;
        while (end>=0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    public static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
            shiftDown(array,parent,array.length);
        }
    }
    public static void shiftDown(int[] array,int parent,int len){
        int child=2*parent+1;
        while (child<len) {
                if (array[child]<array[child+1]&&child+1<len){
                    child++;
            }
                if (array[child]>array[parent]){
                    swap(array,child,parent);
                    parent=child;
                    child=2*parent+1;
                }else {
                    break;
                }
        }
    }
    public static void bubbleSort (int[] array){
        for (int i = 0; i <array.length-1 ; i++) {
            boolean flg = false;
            for (int j = 0; j <array.length-1-i ; j++) {
                if (array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }
            }
            if (!flg){
                break;
            }
        }

    }
    public  void quickSort(int[] array){
        quick(array,0,array.length-1);

    }
    public void quickSort2(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int pivot=partition2(array,left,right);
        if (pivot>left+1){
            stack.push(left);
            stack.push(pivot-1);
        }
        if (pivot<right-1){
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.empty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition2(array, left, right);
            if (pivot > left + 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot < right - 1) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }
    public static int midIndex(int[] array,int left,int right){
        int midIndex=(left+right)/2;
        if (array[left]<array[right]){
            if (array[midIndex]<array[left]){
                return left;
            }else if (array[midIndex]>array[right]){
                return right;
            }else {
                return midIndex;
            }
        }else {
            if (array[midIndex]>array[left]){
                return left;
            } else if (array[midIndex]<array[right]) {
                return right;
            }else {
                return midIndex;
            }
        }
    }
    public static  void inSort(int[] array,int left,int right){
        int tmp=0;
        for (int i = left; i <=right ; i++) {
            tmp=array[i];
            int j = i-1;
            for (; j >=left ; j--) {
                if (array[j]>tmp){
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
    public static void quick(int[] array,int left,int right){
        if (left>=right){
            return;
        }
        if (right-left+1<15){
            inSort(array,left,right);
            return;
        }
        int index=midIndex(array,left,right);
        swap(array,index,left);
        int pivot=partition2(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
    public static int partition(int[] array,int start,int end){
        int i =start;
        int tmp=array[start];
        while (start<end){
            while (start<end&&array[end]>=tmp){
                end--;
            }
            while (start<end&&array[start]<=tmp){
                start++;
            }
            swap(array,start,end);
        }
        swap(array,start,i);
        return start;
    }
    public static int partition2(int[] array,int start,int end){//挖坑法
        int tmp=array[start];
        while (start<end){
            while (start<end&&array[end]>=tmp){
                end--;
            }
            array[start]=array[end];
            while (start<end&&array[start]<=tmp){
                start++;
            }
            array[end]=array[start];
        }
       array[start]=tmp;
        return start;
    }
    public static int partition3(int[] array,int start,int end){//前后指针法
        int tmp=array[start];
        int prev=start;
        int cur = start+1;
        while (cur<=end){
            while (array[cur]<array[start]&&array[++prev]!=array[cur]){
                swap(array,cur,prev);
            }
            cur++;
            }
           array[prev]=tmp;
        return prev;
        }

}
